#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
	int nthUglyNumber(int n) {
		if (!n)
		{
			return n;
		}
		vector<int> ugly(n, 0);
		ugly[0] = 1;
		int i = 0, j = 0, k = 0;
		for (int idx = 1; idx < n; idx++)
		{
			int tmp = min(ugly[i] * 2, min(ugly[j] * 3, ugly[k] * 5));
			if (tmp == ugly[i] * 2) i++;
			if (tmp == ugly[j] * 3) j++;
			if (tmp == ugly[k] * 5) k++;
			ugly[idx] = tmp;
		}
		return ugly[n - 1];
	}
};